package leetcode.new_wrold;

import java.util.ArrayDeque;
import java.util.Deque;

public class T42 {
    public int trap(int[] height) {
        int n = height.length;
        if (n==1){
            return 0;
        }
        int trapRain = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int i=1;
        while (i<n){
            //单调栈入栈
            while (i<n && height[i]<height[stack.getFirst()]){
                System.out.println(height[i]+"进栈");
                stack.push(i++);
            }
            //遇到比栈顶大的出栈
            int pre = stack.getFirst();
            while (i<n && stack.size()!=0 && height[i]>=height[stack.getFirst()]){
                int pop = stack.pop();
                System.out.println(height[pop]+"出栈");
                int y = height[pop]-height[pre];
                System.out.println("trap+"+(y*(i-pop-1)));
                trapRain+=y*(i-pop-1);
                pre = pop;
            }
            if (i<n && stack.size()!=0){
                int y = height[i]-height[pre];
                int x = i-stack.getFirst()-1;
                trapRain+=y*x;
                System.out.println("trap+"+(y*x));
            }
            if (i<n){
                System.out.println(height[i]+"进栈");
            }
            stack.push(i++);

        }

        return trapRain;
    }

    public static void main(String[] args) {
        T42 t42 = new T42();
        int trap = t42.trap(new int[]{5,5,1,7,1,1,5,2,7,6});
        System.out.println(trap);
    }
}

